/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._654;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
 * <p>
 * 二叉树的根是数组中的最大元素。
 * 左子树是通过数组中最大值左边部分构造出的最大二叉树。
 * 右子树是通过数组中最大值右边部分构造出的最大二叉树。
 * 通过给定的数组构建最大二叉树，并且输出这个树的根节点。
 * <p>
 *  
 * <p>
 * 示例 ：
 * <p>
 * 输入：[3,2,1,6,0,5]
 * 输出：返回下面这棵树的根节点：
 * <p>
 * 6
 * /   \
 * 3     5
 * \    /
 * 2  0
 * \
 * 1
 *  
 * <p>
 * 提示：
 * <p>
 * 给定的数组的大小在 [1, 1000] 之间。
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._654
 * @ClassName: MaximumBinaryTree
 * @Author: linyaonan
 * @Date: 2020/1/20 11:04
 */
public class MaximumBinaryTree {
    HashMap<Integer, Integer> map;

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        // 1.对原始数组的下标进行统计。同时生成用于传递的copy数组
        int[] copy = new int[nums.length];
        map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            copy[i] = nums[i];
            // 记录数据下标
            map.put(nums[i], i);
        }
        // 升序排序
        Arrays.sort(copy);
        TreeNode build = build(nums, 0, nums.length - 1);
        return build;
    }

    private TreeNode build(int[] org, int orgStart, int orgEnd) {
        if (orgStart > orgEnd) {
            return null;
        } else {
            // 2.对数组重新进行筛选
            int[] copy = new int[orgEnd - orgStart + 1];
            int inIndex = 0;
            for (int i = orgStart; i <= orgEnd; i++) {
                copy[inIndex++] = org[i];
            }
            // 排序
            Arrays.sort(copy);
            // 找出根节点
            int rootValue = copy[copy.length - 1];
            TreeNode root = new TreeNode(rootValue);
            Integer rootIndex = map.get(rootValue);
            // 3.构建左树
            root.left = build(org, orgStart, rootIndex - 1);
            root.right = build(org, rootIndex + 1, orgEnd);
            return root;
        }

    }

}
